package com.fps.webshop.question.question0001_0099;

import java.util.Deque;
import java.util.LinkedList;

import com.fps.webshop.question.common.TreeNode;

/**
 * 98. 验证二叉搜索树
 * 
 * 给定一个二叉树，判断其是否是一个有效的二叉搜索树。
 * 
 * 假设一个二叉搜索树具有如下特征：
 * 
 * 节点的左子树只包含小于当前节点的数。
 * 节点的右子树只包含大于当前节点的数。
 * 所有左子树和右子树自身必须也是二叉搜索树。
 * 
 * 示例 1:
 * 输入:
 *     2
 *    / \
 *   1   3
 * 输出: true
 * 
 * 示例 2:
 * 输入:
 *     5
 *    / \
 *   1   4
 *      / \
 *     3   6
 * 输出: false
 * 解释: 输入为: [5,1,4,null,null,3,6]。
 *      根节点的值为 5 ，但是其右子节点值为 4 。
 */
public class Question098 {
	
	/**
	 * 第一次提交，二叉树递归
	 * 
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注
	 * 通过		0 ms	37.9 MB	Java	2021/08/24 14:16
	 * 
	 * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
	 * 内存消耗：37.9 MB, 在所有 Java 提交中击败了81.91%的用户
	 */
	public static boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    public static boolean isValidBST(TreeNode node, long lower, long upper) {
        if (node == null) {
            return true;
        }
        if (node.val <= lower || node.val >= upper) {
            return false;
        }
        return isValidBST(node.left, lower, node.val) && isValidBST(node.right, node.val, upper);
    }
    
    
    /**
	 * 第2次提交，二叉树中序遍历
	 * 如果是二叉搜索树，那么中序遍历得到的一定是一个升序的数组
	 * 
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注
	 * 通过		1 ms	38.1 MB	Java	2021/08/24 14:19
	 * 
	 * 执行用时：1 ms, 在所有 Java 提交中击败了30.74%的用户
	 * 内存消耗：38.1 MB, 在所有 Java 提交中击败了31.87%的用户
	 */
    public boolean isValidBST2(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        double inorder = -Double.MAX_VALUE;

        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
              // 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树
            if (root.val <= inorder) {
                return false;
            }
            inorder = root.val;
            root = root.right;
        }
        return true;
    }

	public static void main(String[] args) {
		TreeNode root = new TreeNode(51);
		TreeNode leftNode1 = new TreeNode(4);
		TreeNode rightNode1 = new TreeNode(6);
		root.left = leftNode1;
		root.right = rightNode1;
		
		//TreeNode rightNode2 = new TreeNode(67);
		//leftNode1.right = rightNode2;
		
		TreeNode leftNode3 = new TreeNode(3);
		TreeNode rightNode3 = new TreeNode(7);
		rightNode1.left = leftNode3;
		rightNode1.right = rightNode3;
		
		System.out.print(isValidBST(root));
		
	}
}
